package leetcode8;

public class test44 {
    /**
     * 105. 从前序与中序遍历序列构造二叉树
     * @param preorder
     * @param inorder
     * @return
     */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return helper(preorder, 0, preorder.length, inorder, 0, inorder.length);
    }
    public TreeNode helper(int[] preorder,int pre_start,int pre_end,int[] inorder,int in_start,int in_end){
        if(pre_start == pre_end){
            return null;
        }
        int root_val = preorder[pre_start];
        int in_index = 0;
        for(int i = in_start;i < in_end;i++){
            if(root_val == inorder[i]){
                in_index = i;
                break;
            }
        }
        TreeNode root = new TreeNode(root_val);
        int left_num = in_index - in_start;
        root.left = helper(preorder,pre_start + 1,pre_start + left_num + 1,inorder,in_start,in_index);
        root.right = helper(preorder,pre_start + left_num + 1,pre_end,inorder,in_index + 1,in_end);
        return root;
    }
}
